package main.java.LeetCode.ClassicalAlgorithm.Sort.Impl;


import main.java.LeetCode.ClassicalAlgorithm.Sort.Sort;

@SuppressWarnings("ALL")
public class MergeSort implements Sort {

    private final String NAME = "MergeSort";
    @Override
    public void sort(int[] arr) {
        doSort(arr,0, arr.length-1);
        System.out.print(NAME+": ");
        for(int num:arr){
            System.out.print(num+" ");
        }
        System.out.println();
    }

    private int[] doSort(int[] arr,int start,int end){
        if(start==end){
            int[] res = new int[1];
            res[0] = arr[start];
            return res;
        }

        int mid = (start+end)/2;
        int[] left = doSort(arr,start,mid);
        int[] right = doSort(arr,mid+1,end);

        int[] res = new int[left.length+right.length];

        int indexL = 0;
        int indexR = 0;
        int index = 0;

        while (indexL<left.length&&indexR<right.length){
            int valL = left[indexL];
            int valR = right[indexR];
            if(valL<valR){
                res[index] = valL;
                indexL++;
            }else {
                res[index] = valR;
                indexR++;
            }
            index++;
        }

        while (index<res.length&&indexL<left.length){
            res[index] = left[indexL];
            index++;
            indexL++;
        }
        while (index<res.length&&indexR<right.length){
            res[index] = right[indexR];
            index++;
            indexR++;
        }

        for(int i = 0;i<res.length;i++){
            arr[start] = res[i];
            start++;
        }
        return res;
    }
}
